1. Field of the Invention
This invention relates generally to data store buffer systems and specifically to a direct access store buffer memory that adapts to changes in data store access patterns to optimize predictive buffer hit rates.
2. Discussion of the Related Art
In most computer systems, the processor operates on data received from some data store, such as a Direct Access Storage Device (DASD), an optical disk drive, or the like. The processor operates at high speed relative to the usual data store, which motivates the computer system designer to include all available means for increasing data store speed to reduce processor waiting time. Waiting time can be reduced by using high-speed (expensive) data store technology such as high-speed Random Access Memory (RAM) as an intermediate cache or buffer memory between data store and processor. Waiting time may also be reduced by anticipating the data to be requested and "prefetching" them to the buffer memory from the data store before arrival of a data request from the processor.
Most DASDs and optical disk drives are equipped with a RAM buffer memory or "look-ahead buffer" partitioned into many segments. Each segment is used for look-ahead prefetching of data blocks from the data storage medium. A DASD or optical disk drive buffer memory provides "read" prefetching of data by continuing to read subsequent consecutive data sectors into the buffer memory in anticipation of possible future use after completing the initial read request received from the processor. This prefetching strategy is additional to any segment selection strategy based on Least Recently Used (LRU) or other replacement procedures.
The usual predictive buffer memory management technique saves all or the last portion of the currently requested data in an active buffer memory segment and continues to prefetch subsequent data sectors into the remainder of the active segment in consecutive order. This can be accomplished efficiently in mechanically-operated data stores because the two fetch and prefetch operations require only a single mechanical read-head disk access. Thus, for any single Data Access Request (DAR), the data store first fetches the requested data blocks and stores at least the last portion thereof in a buffer memory segment. After completion of the fetch operation, the data store continues to read in consecutive order sufficient additional subsequent data blocks to fill the active buffer memory segment. The prefetching step ends either when the active buffer memory segment is completely filled or when the next DAR arrives (if the next DAR is not a buffer hit). If the next DAR is a buffer "hit", the requested data is retrieved from the buffer memory segment and prefetching may continue uninterrupted because no new data store access is necessary. If the next DAR is not a buffer hit (i.e., is a buffer "miss"), a new data store fetching access is initiated for a new buffer segment and the requested data blocks are returned to the newly active buffer segment, leaving undisturbed the fetched and prefetched data blocks in the formerly active buffer segment for possible future hits. The newly active buffer memory segment is selected from among many such segments by using some sort of LRU selection procedure or the like.
This predictive buffer memory management scheme is quite efficient if the data access pattern provides reasonable likelihood that the data block requested in the current DAR will soon be again requested (a "repeated" access). Such a "re-use" buffer memory hit is efficient because no new data store access is necessary. An example of such a repeated Nonsequential Access Pattern (NAP) to several Logical Block Addresses (LBAs) is "read LBA5, read LBA8, read LBA700, read LBA5". The first DAR (read LBA5) results in a data store access to fetch LBA5, which is then stored in a first buffer memory segment. After fetching LBA5, the subsequent LBAs 6-36 are consecutively prefetched and stored in the same first buffer memory segment (presuming a segment capacity of 32 LBAs). When the second DAR (LBA8) arrives, the requested data is retrieved directly from the first buffer memory segment, having been prefetched. When the third DAR arrives (read LBA700), a second data store access is initiated to fetch LBA700, which is then stored in a second buffer memory segment together with the 31 consecutive subsequent LBAs 701-731. Finally, when the fourth DAR arrives (read LBA5), the data is retrieved directly from the first buffer memory segment, which has not yet been disturbed. As more DARs arrive, the first buffer segment is soon overwritten in response to LRU selection for one of the new DARs. Thus, unless data block requests are frequently repeated, this predictive buffer memory management scheme contributes little to overall data store efficiency.
A predictive buffer strategy is often preferred because (a) it requires no more than the data store accesses otherwise required for the "fetched"data to retrieve the next few data blocks in consecutive order from the data store medium and (b) the DAR access pattern is often "sequential", consisting of a series of DARs for data blocks stored consecutively in the data store medium. An example of a Sequential Access Pattern (SAP) is "read LBA100, read LBA101, read LBA102, . . . " and so forth for many DARs. Assuming that each buffer memory segment has a 32-block capacity, the above-described predictive buffer memory management scheme first fetches LBA100 into a first buffer memory segment and then prefetches LBA101-131 into the same first buffer memory segment, thereby filling it to capacity and halting the prefetching activity, ending the one necessary data store access operation. Advantageously, the next 31 DARs (read 101, read 102, . . . , read 131) hit in the first buffer memory segment. A problem occurs when the 33rd DAR (read LBA132) arrives. Because this DAR misses the buffer memory, a second data store access operation is initiated to fetch LBA132 (and to prefetch LBA133-163) into a second buffer memory segment. This second data store access operation requires substantial time (in terms of processor speed) and slows data store performance because of an unavoidable "hiccup" in buffer memory hits at every 33rd DAR in long sequential data access patterns.
The above-described predictive management strategy is optimal for Nonsequential Access Patterns (NAPs) but can be revised to improve efficiency for DARs arriving in Sequential Access Patterns (SAPs) through the use of a "circular" predictive buffer management scheme. The circular buffer memory management scheme monitors the active buffer memory segment for a read hit anywhere in the segment. When the hit is detected, all logical buffer memory segment space preceding the hit data block is immediately released for use in storing additional prefetched data blocks without activating a new buffer segment. This can be understood by considering each buffer memory segment to be a "wrap-around" segment wherein all space ahead of the hits is immediately filled with subsequent data blocks prefetched from the data store medium. When the physical end of the buffer memory segment is encountered, it is logically wrapped around to join the physical beginning, giving rise to the denomination "circular buffer". This circular buffer memory management scheme is optimal for SAPs because sequential prefetching of data blocks can continue in one uninterrupted disk access so long as new DARs arrive requesting data blocks in consecutive sequence, thereby eliminating the hiccup problem. Consecutive data blocks may be continuously prefetched into the buffer memory segment so long as incoming DARs continue to request sequential data blocks, but Nonsequential (repeated) Access Patterns (NAPs) are not efficiently handled because each buffer data block is immediately overwritten instead of remaining in memory to provide a hit for a repeated access request. Accordingly, there is a clearly-felt need in the art for a predictive buffer memory management scheme that optimally supports both sequential access patterns (SAPs) and nonsequential (repeated) access patterns (NAPs) in a data store system. The circular management scheme known in the art uses a Circular Overwrite Mode (COM) as discussed above. The predictive segment scheme known in the art uses a Block Overwrite Mode (BOM) as discussed above. The COM is inconsistent with the BOM in a segmented buffer memory even though a BOM memory approaches a single-segment COM buffer as it is reconfigured into ever-larger numbers of ever-smaller segments if a Least Recently Used (LRU) segment allocation procedure is employed.
Practitioners in the art have proposed adjusting the segment or block size in a BOM buffer memory intended to operate with NAPs. For instance, in U.S. Patent No. 5,285,527, William R. Crick et al. disclose a predictive historical cache memory system with circular buffer characteristics for use as a part historical, part predictive cache memory for processor instruction execution. Crick et al. provide the usual circular memory management capability for efficient retrieval of sequential instructions because processor instructions are typically retrieved and executed sequentially. Because instruction flow is often interrupted by conditional and unconditional branch instructions, they also provide means for disabling the block prefetching operation upon detection of such an interruption in sequential flow. Crick et al. continuously compare the location of the last instruction executed and the last instruction prefetched, disabling the prefetching operation whenever the two instruction addresses diverge by predetermined amount. While this method avoids unnecessary loss of historical buffer memory elements, Crick et al. neither consider nor suggest modified prefetching of instructions when the access pattern diverges.
Similarly, in U.S. Patent No. 5,003,471, Gibson discloses an intermediate data buffer with a sliding "windowed programmable data buffer (WPDB)" that operates as a programmable circular data buffer that can be adjusted in size and location within the buffer memory. Gibson's WPDB may be programmed to increment forward around the buffer memory or remain stationary and may operate in either of two modes: one mode using offsets to access data within the window and another using offsets to access the window itself, permitting prefetching and storage of data through a First-In-First-Out (FIFO) buffer. Gibson's windowing scheme is directed primarily to a cache management scheme that permits the use of short address segments by the processor and he neither considers nor suggests means for optimizing buffer management responsive to access patterns.
In U.S. Patent No. 4,377,852, Thompson discloses a communications control system that includes means for the interrupt-control of a circular buffer in a text scrolling control system. Thompson proposes operator-controlled switching of circular buffer operation from "wrap-on" to "wrap-off" modes, both of which operate intelligently to preserve the textual display characteristics of data columns as originally received. Thompson neither considers nor suggests methods for adaptively managing his buffer memory responsive to data access patterns. Similarly, in European Patent Application No. 0 517 473 A2, Bruce R. Peterson et al. disclose a programmable data sequencer for transferring fixed-length data blocks between variable-length storage locations and a buffer memory within a data store system. Peterson et al. consider the problem of automatic data block sequencing in a Zone-Band Recording (ZBR) disk storage scheme where data block characteristics vary by location within the data store medium. They neither consider nor suggest means for adaptive buffer memory management responsive to changes in data access patterns, limiting their concern to processor-controlled variable-length data blocking.
Accordingly, there remains a clearly-felt need in the art for a technique suitable for automatically adapting buffer memory operation to changes in incoming data access patterns, including a suitable method for detecting changes in such patterns. These unresolved deficiencies are clearly felt in the art and are solved by this invention in the manner described below.